 
 
#include <iostream>
#include "FunctionList.h"
#include "Event.h"

using namespace std;

void BubbleSort(Event** array, int length) {
      int i, j, flag = 1;    // set flag to 1 to start first pass
      Event* temp;             // holding variable
      for(i = 1; (i <= length) && flag; i++) {
          flag = 0;
          for (j=0; j < (length -1); j++) {
             if (array[j+1]->Cycle < array[j]->Cycle) {      
                    temp = array[j];             
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = 1;
               }
          }
     }
}

bool computeSelfAndChildrenExecTime(FunctionList* list, string main_function) {  
     
  // Create the set of events (entry in a function or exit from a function).
  long length = list->getLength() * 2;
  Event** event_array = new Event*[length];
  Function* f = list->getFirstFunction();
  for (int i=0 ; i < length ; i+=2) {
      event_array[i] = new Event(f->StartCycle, 1, f);
      event_array[i+1] = new Event(f->EndCycle, 2, f);
      f = list->getNextFunction();
  }

  cout << "Create the set of events (entry and exit) from the traces: DONE" << endl;   
  
  // Sort all the events in chronological order.
  BubbleSort(event_array, length);
    
  cout << "Sort the events in chronological order: DONE" << endl;
    
  // Parse the function call tree and filter out all the functions that are not of interest  
  FunctionList* stack = new FunctionList();
  bool END_ALGO = false; 
  bool RECORD = false;
  for (int i=0 ; i < length && !END_ALGO; ++i) {
     if (event_array[i]->Type == 1) { // Entry in a function
        if (strcmp(event_array[i]->Fct->FunctionName.c_str(), main_function.c_str()) == 0) RECORD = true;
        if (RECORD) stack->addFront(event_array[i]->Fct);    
        else event_array[i]->Fct->ToBeFilteredOut = true;
        //cout << "Entry in function " << event_array[i]->Fct->FunctionName << " and RECORD = " << RECORD << endl;    
     }        
     else if (event_array[i]->Type == 2) { // Exit from a function
        if (RECORD) {
           Function* f_closing = event_array[i]->Fct;
           Function* f_opened = stack->pop();
           if (f_closing != f_opened) {
              cout << "The traces are not coherent." << endl;
              cout << "Function " << f_opened->FunctionName << " starts at cycle " << f_opened->StartCycle << " and finishes at cycle " << f_opened->EndCycle << " while Function " << f_closing->FunctionName << " starts at cycle " << f_closing->StartCycle << " and finishes at cycle " << f_closing->EndCycle << endl; 
              END_ALGO = true;             
           }
           else {
              f_opened->SelfExecTime = f_opened->SelfChildrenExecTime - f_opened->ChildrenExecTime;
              for (Function* f_stack = stack->getFirstFunction(); f_stack; f_stack = stack->getNextFunction()) {
                 f_stack->ChildrenExecTime += f_opened->SelfExecTime; 
              }
              //cout << "Exit from function " << f_opened->FunctionName << " and RECORD = " << RECORD;
              if (strcmp(f_opened->FunctionName.c_str(), main_function.c_str()) == 0) RECORD = false;
              //cout << ", and now RECORD = " << RECORD << endl;
           }
        }
     }
  }
  stack->detachAllFunctions();
  delete stack;  
  for (int i=0 ; i < length ; ++i) delete event_array[i];
  delete[] event_array;
  
  cout << "Re-compute the missing information for all functions: DONE" << endl;
  
  // Filter out all the unecessary functions.
  
  list->filterOutFunctions();
  
  cout << "Filter out non-studied functions: DONE" << endl;
  
  return !END_ALGO;
}



int main(int argc, char* argv[]) {
  string input_filename;
  string output_filename;      
  string main_function;
  if (argc != 4) { 
      std::cout << "Usage is: augment-traces <infile> <outfile> MAIN_FUNCTION_NAME \n";
      exit(0);
  } else { 
      input_filename = argv[1];
      output_filename = argv[2];
      std::string s(argv[3]);
      main_function = s;
  }
  
  // Check if input file exists
  std::ifstream f_ex(input_filename.c_str());
  bool file_exists = f_ex.good();
  f_ex.close();
  if (!file_exists) {
     cout << "Error: input file does not exist" << endl;
     exit(0);
  }
  
  // Read the traces in the input_filename. 
  /* The format of these traces is:
         #CYCLE END_CYCLE TRACE_NAME FUNCTION
     with headers!
  */     
  
  FunctionList* list = new FunctionList();
  list->load(input_filename);
  
  cout << "Load the traces: DONE" << endl;
  
  bool success = computeSelfAndChildrenExecTime(list, main_function); // This procedure also filter out all functions that are not of interest when studying the target function "main_function".
  // Save all these values in a temporary file 
  if (success) {
     list->mirror();
     list->save("_data.txt");
  }
  
  cout << "Save re-constructed information in _data.txt: DONE" << endl;
  
  // Create a table with the desired format, i.e. a table with N row and M column where N is the number of run of the target function "main_function" and M is the number of different functions called during all the executions of that main_function
  // Initialize that table to 0 and create a header vector with all the function names
  
  long** tab_results;
  string* tab_header;
  long nb_traces = list->nbOccurrence(main_function);
  FunctionList* all_functions = new FunctionList();
  for (int i = 0; i < nb_traces; ++i) all_functions->getOneOfEachFunction(list);
  all_functions->mirror();
  long nb_functions = all_functions->getLength();
  tab_results = new long*[nb_traces];
  for (int i = 0; i < nb_traces; ++i) {
      tab_results[i] = new long[nb_functions];
      for (int j = 0; j < nb_functions; j++) tab_results[i][j] = 0;
  }
  tab_header = new string[nb_functions];
  int index=0;
  for (Function* f = all_functions->getFirstFunction(); f; f = all_functions->getNextFunction()) {
      tab_header[index] = f->FunctionName;
      index++;
  }
  all_functions->detachAllFunctions();
  delete all_functions;
  
  cout << "Create the output table for the statistics: DONE" << endl;
  
  // Compute and fill in the numbers in the table
  
  int num_run = -1;
  for (Function* f = list->getFirstFunction(); f; f = list->getNextFunction()) {
      if (strcmp(main_function.c_str(), f->FunctionName.c_str()) == 0) {
         num_run++;
      }
      int fct_index = 0;
      bool fct_found = false;
      for (int i = 0; i < nb_functions && !fct_found; ++i) {
          if (strcmp(f->FunctionName.c_str(), tab_header[i].c_str()) == 0) {
             fct_found = true;
             fct_index = i;
          }
      }
      if (!fct_found) {
         cout << "Error: function not found" << endl;
         exit(0);
      }
      tab_results[num_run][fct_index] += f->SelfExecTime;
  }

  cout << "Fill in the table with the statistics: DONE" << endl;
  
  // Save the table in the output file

  ofstream myfile;
  myfile.open(output_filename.c_str());
  for (int i = 0; i < nb_functions - 1; ++i) myfile << tab_header[i] << " ";
  myfile << tab_header[nb_functions-1] << endl;
  
  for (int i = 0; i < nb_traces; ++i) {
      for (int j = 0; j < nb_functions - 1; ++j) myfile << tab_results[i][j] << " ";
      myfile << tab_results[i][nb_functions-1] << endl;
  }  
  myfile.close();
  
  cout << "Statistics saved in the output file: DONE" << endl;
  
  // Delete all the working variables
     
  for (int i = 0; i < nb_traces; ++i) delete[] tab_results[i];
  delete[] tab_results;
  delete[] tab_header;     
  delete list;
  
  return 0;
}
